package jpnms.src;

import org.junit.Test;

import java.time.Duration;
import java.time.Instant;
import java.util.*;
import java.util.regex.Pattern;

public class BaseAlgo {
    /**
     * 稀疏数组转换 ——》 count row col
     *
     * @param chessArr
     * @return
     */
    public int[][] chess2Sparse(int[][] chessArr) {
        ArrayList<int[]> resu = new ArrayList<>();
        int count = 0;
        for (int row = 0; row < chessArr.length; row++) {
            for (int col = 0; col < chessArr[0].length; col++) {
                if (0 != chessArr[row][col]) {
                    count++;
                    resu.add(new int[]{chessArr[row][col], row, col});
                }
            }
        }

        int[][] resuArr = new int[count + 1][3];
        resu.add(0, new int[]{count, chessArr.length, chessArr[0].length});
        resu.toArray(resuArr);
        return resuArr;
    }

    /**
     * 解析稀疏数组 ——》count row col
     *
     * @param spares
     * @return
     */
    public int[][] sparse2Chess(int[][] spares) {
        int[][] chess = new int[spares[0][1]][spares[0][2]];
        for (int i = 1; i < spares.length; i++) {
            int[] row = spares[i];
            chess[row[1]][row[2]] = row[0];
        }
        return chess;
    }

    public void printArr(int[][] arr) {
        for (int[] row :
                arr) {
            for (int data :
                    row) {
                System.out.printf("%-2d\t", data);
            }
            System.out.println("");
        }
    }

    @Test
    public void testChessSparse() {
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;

        int[][] ints = chess2Sparse(chessArr);
        int[][] ints1 = sparse2Chess(ints);
        printArr(ints1);
    }

    @Test
    public void testStack() {
//        LinkedStack  as= new LinkedStack(10);
        ArrayStack as = new ArrayStack(5);
        as.push(343);
        as.push(3433);
        as.push(34433);
        as.push(34363);
        as.push(3437873);
        as.push(343989);
        as.pop();
        as.pop();
        as.pop();
        System.out.println(as);
    }

    @Test
    public void testCalc() {
//            String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        ReversePolishMultiCalc rCacl = new ReversePolishMultiCalc();
        try {
            rCacl.doCalc(rCacl.doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    @Test
    public void testCheck() {
        Queue8 queue8 = new Queue8();
        queue8.check(0); // 从第 1 行开始放置
    }

    /**
     * 冒泡排序：每进行一次冒泡，排好一个最大值
     *
     * @param arr
     */
    public void bubbleSort(int[] arr) {
        int tmp = 0;
        boolean change = false;
        for (int i = 0; i < arr.length - 1; i++) {
            change = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    change = true;
                }
            }
            if (!change) break;
        }
    }

    /**
     * 选择排序：每次找出最小值，并与第n个值交换
     *
     * @param arr
     */
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int tmp = i;
            for (int j = i + 1; j < arr.length - 1; j++) {
                tmp = arr[tmp] > arr[j] ? j : tmp;
            }
            int temp = arr[tmp];
            arr[tmp] = arr[i];
            arr[i] = temp;
        }


    }

    /**
     * 插入排序：无序部分后插至有序部分，每次后移部分有序数据
     *
     * @param arr
     */
    public void insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            // 只是将这两句代码的代表当前要插入的下标用外循环的变量来代替了
            int curval = arr[i];
            int sortIdx = i - 1;
            //当前待插入值更小时，有序部分后移
            while (sortIdx >= 0 && curval < arr[sortIdx]) {
                arr[sortIdx + 1] = arr[sortIdx];
                sortIdx--;
            }
            arr[sortIdx + 1] = curval;//插入待插入值
        }
    }

    /**
     * 希尔排序：插排的改进，分组+插排
     */
    public void shellSort(int[] arr) {
        //按gap分组,gap倍数衰减
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //对每个分组进行插排
            for (int i = gap; i < arr.length; i++) {
                int curval = arr[i];
                int sortIdx = i - gap;
                //当前待插入值更小时，有序部分后移
                while (sortIdx >= 0 && curval < arr[sortIdx]) {
                    arr[sortIdx + gap] = arr[sortIdx];
                    sortIdx -= gap;
                }
                arr[sortIdx + gap] = curval;//插入待插入值
            }
        }
    }

    /**
     * sort algo
     * 内部排序（内存）
     * 插入排序
     * 直接插入排序
     * 希尔排序
     * 简单选择排序
     * 堆排序
     * 交换排序
     * 选择排序 n^2
     * 冒泡排序 n^2
     * 快速排序
     * 归并排序
     * 基数排序
     * 外部排序（使用内存和外存结合）
     */

    /**
     * 快速排序：冒泡的改进,太难了，不会写
     */
    public void quickSort(int[] arr, int left, int right) {
        int pivotIndex = (left + right) / 2;
        int pivot = arr[pivotIndex];
        int l = left;
        int r = right;
        while (l < r) {
            // 从左往右找，直到找到一个数，比基准值大的数
            while (arr[l] < pivot) l++;
            // 从右往左找，知道找到一个数，比基准值小的数
            while (arr[r] > pivot) r--;
            // 表示未找到
            if (l >= r) break;
            // 进行交换
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            // 那么下一轮，左侧的这个值将不再参与排序，因为刚交换过，一定比基准值小
            // 那么下一轮，右侧的这个值将不再参与排序，因为刚交换过，一定比基准值大
            r--;
            l++;
        }
        // 当一轮找完后，没有找到，则是中间值时，
        // 需要让他们插件而过，也就是重新分组，中间值不再参与分组
        // 否则，在某些情况下，会进入死循环
        if (l == r) {
            l++;
            r--;
        }
        // 如果左侧还可以继续分组，则继续快排
        // 由于擦肩而过了，那么左侧的组值，则是最初的开始与中间值的前一个，也就是这里得到的 r
        if (left < r) quickSort(arr, left, r);
        if (right > l) quickSort(arr, l, right);

    }

    @Test
    public void test() {
        LinkedList<Integer> it = new LinkedList<>();
        it.add(6);
        it.add(1, 6);
        System.out.println(it.size());
        System.out.println(it.get(0));
        System.out.println(it);
        int[] as = new int[it.size()];

    }

    @Test
    public void testSort() {
        int max = 80_000;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80_000);
        }
//        int [] arr =new int[]{6,7,8,5,6,8,9};

        Instant startTime = Instant.now();
//        bubbleSort(arr);
//        selectSort(arr);
//        insertSort(arr);
//        shellSort(arr);
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        Instant endTime = Instant.now();
        System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");

    }

    /**
     * 链表
     */

    public class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 数组实现栈
     */
    public class ArrayStack {
        int[] stack;
        int maxSize;
        int top = -1;

        public ArrayStack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }

        public boolean isFull() {
            return maxSize - 1 == top;
        }

        public boolean isEmpty() {
            return -1 == top;
        }

        public void push(int val) {
            if (isFull()) {
                System.out.println("full");
                return;
            }
            stack[++top] = val;
        }

        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("empty");
            }
            return stack[top--];
        }

        @Override
        public String toString() {
            if (isEmpty()) return "";
            StringBuilder str = new StringBuilder();
            for (int i = top; i >= 0; i--) {
                str.append(stack[i] + "\n");
            }
            return new String(str);
        }
    }

    /**
     * 链表实现栈
     */
    public class LinkedStack {
        int size;
        int maxSize;
        Node top;

        public LinkedStack(int maxSize) {
            this.maxSize = maxSize;
        }

        public boolean isFull() {
            return maxSize == size;
        }

        public boolean isEmpty() {
            return 0 == size;
        }

        public void push(int val) {
            if (isFull()) {
                System.out.println("full");
                return;
            }
            Node tmp = top;
            top = new Node(val);
            top.next = tmp;
            size++;
        }

        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("empty");
            }
            Node tmp = top;
            top = top.next;
            size--;
            return tmp.value;
        }

        public String toString() {
            if (isEmpty()) return "";
            Node tmp = top;
            StringBuilder str = new StringBuilder();
            while (tmp != null) {
                str.append(tmp.toString() + "\n");
                tmp = tmp.next;
            }
            return new String(str);
        }

        class Node {
            int value;
            Node next;

            public Node(int value) {
                this.value = value;
            }

            @Override
            public String toString() {
                return "Node{" +
                        "value=" + value +
                        '}';
            }
        }
    }

    /**
     * <pre>
     * 完整版的逆波兰计算器，功能包括
     * 支持 + - * / ( )
     * 多位数，支持小数,
     * 兼容处理, 过滤任何空白字符，包括空格、制表符、换页符
     *
     * 逆波兰计算器完整版考虑的因素较多，下面给出完整版代码供同学们学习，其基本思路和前面一样，也是使用到：中缀表达式转后缀表达式。
     * </pre>
     */
    public class ReversePolishMultiCalc {
        static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";
        static final String LEFT = "(";
        static final String RIGHT = ")";
        static final String ADD = "+";
        static final String MINUS = "-";
        static final String TIMES = "*";
        static final String DIVISION = "/";

        /**
         * 加減 + -
         */
        final int LEVEL_01 = 1;
        /**
         * 乘除 * /
         */
        final int LEVEL_02 = 2;
        /**
         * 括号
         */
        final int LEVEL_HIGH = Integer.MAX_VALUE;
        Stack<String> stack = new Stack<String>();
        List<String> data = Collections.synchronizedList(new ArrayList<String>());

        /**
         * 去除所有空白符
         *
         * @param s
         * @return
         */
        public String replaceAllBlank(String s) {
            // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
            return s.replaceAll("\\s+", "");
        }

        /**
         * 判断是不是数字 int double long float
         *
         * @param s
         * @return
         */
        public boolean isNumber(String s) {
            // 以-、+号开头匹配0或1次,匹配任意次【数字、小数点】
            Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
            return pattern.matcher(s).matches();
        }

        /**
         * 判断是不是运算符
         *
         * @param s
         * @return
         */
        public boolean isSymbol(String s) {
            return s.matches(SYMBOL);
        }

        /**
         * 匹配运算等级
         *
         * @param s
         * @return
         */
        public int calcLevel(String s) {
            if ("+".equals(s) || "-".equals(s)) {
                return LEVEL_01;
            } else if ("*".equals(s) || "/".equals(s)) {
                return LEVEL_02;
            }
            return LEVEL_HIGH;
        }

        /**
         * 匹配
         *
         * @param s
         * @throws Exception
         */
        public List<String> doMatch(String s) throws Exception {
            if (s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
            if (!isNumber(s.charAt(0) + "")) throw new RuntimeException("data illeagle,start not with a number");

            s = replaceAllBlank(s);

            String each;
            int start = 0;

            for (int i = 0; i < s.length(); i++) {
                if (isSymbol(s.charAt(i) + "")) {
                    each = s.charAt(i) + "";
                    //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                    if (stack.isEmpty() || LEFT.equals(each)
                            || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)) {
                        stack.push(each);
                    } else if (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                        //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                        while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                            if (calcLevel(stack.peek()) == LEVEL_HIGH) {
                                break;
                            }
                            data.add(stack.pop());
                        }
                        stack.push(each);
                    } else if (RIGHT.equals(each)) {
                        // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                        while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())) {
                            if (LEVEL_HIGH == calcLevel(stack.peek())) {
                                stack.pop();
                                break;
                            }
                            data.add(stack.pop());
                        }
                    }
                    start = i;    //前一个运算符的位置
                } else if (i == s.length() - 1 || isSymbol(s.charAt(i + 1) + "")) {
                    each = start == 0 ? s.substring(start, i + 1) : s.substring(start + 1, i + 1);
                    if (isNumber(each)) {
                        data.add(each);
                        continue;
                    }
                    throw new RuntimeException("data not match number");
                }
            }
            //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
            Collections.reverse(stack);
            data.addAll(new ArrayList<>(stack));

            System.out.println(data);
            return data;
        }

        /**
         * 算出结果
         *
         * @param list
         * @return
         */
        public Double doCalc(List<String> list) {
            Double d = 0d;
            if (list == null || list.isEmpty()) {
                return null;
            }
            if (list.size() == 1) {
                System.out.println(list);
                d = Double.valueOf(list.get(0));
                return d;
            }
            ArrayList<String> list1 = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                list1.add(list.get(i));
                if (isSymbol(list.get(i))) {
                    Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                    list1.remove(i);
                    list1.remove(i - 1);
                    list1.set(i - 2, d1 + "");
                    list1.addAll(list.subList(i + 1, list.size()));
                    break;
                }
            }
            doCalc(list1);
            return d;
        }

        /**
         * 运算
         *
         * @param s1
         * @param s2
         * @param symbol
         * @return
         */
        public Double doTheMath(String s1, String s2, String symbol) {
            Double result;
            switch (symbol) {
                case ADD:
                    result = Double.valueOf(s1) + Double.valueOf(s2);
                    break;
                case MINUS:
                    result = Double.valueOf(s1) - Double.valueOf(s2);
                    break;
                case TIMES:
                    result = Double.valueOf(s1) * Double.valueOf(s2);
                    break;
                case DIVISION:
                    result = Double.valueOf(s1) / Double.valueOf(s2);
                    break;
                default:
                    result = null;
            }
            return result;

        }
    }

    /**
     * Recursion:递归
     * 传入变量必须不同
     * 虚拟机内存：每执行到一个方法，就开辟一个独立空间（可看成栈）
     * 八皇后问题——回溯算法
     */
    public class Queue8 {
        // 共有多少个皇后
        int max = 8;
        /**
         * 存放皇后位置的结果
         * <pre>
         * 下标：表示棋盘中的某一行
         * 对应的值：表示在这一行上，该皇后摆放在哪一列
         * 比如：array[0] = 1，表示在第 1 行的第 2 列上摆放了一个皇后
         *
         * 由于规则，一行只能有一个皇后，所以可以使用一维数组来代替二维数组的棋盘结果
         * </pre>
         */
        int[] array = new int[max];
        int count = 0; // 统计有多少个结果

        /**
         * 放置第 n 个（行）皇后
         *
         * @param n
         */
        private void check(int n) {
            // n = 8，那么表示放第 9 个皇后，8 个皇后已经放完了
            // 表示找到了一个正确的结果，打印这个结果，并返回
            if (n == max) {
                count++;
                print();
                return;
            }
            // 开始暴力对比，从该行的第一列开始尝试放置皇后，直到与前面所放置的不冲突
            for (int i = 0; i < max; i++) {
                // 在该行的第 i 列上放置一个皇后
                array[n] = i;
                // 检测与已经放置的是否冲突
                if (judge(n)) {
                    // 如果不冲突，则表示该行的皇后放置没有问题
                    // 开始进入下一行的皇后放置
                    check(n + 1);
                }
                // 如果冲突，这里什么也不做
                // 因为是从第一列开始放置，如果冲突，则尝试放置到第 2 列上，直到放置成功
            }
        }

        /**
         * 判定要放置的这一个皇后，和前面已经摆放的位置是否冲突
         *
         * @param n 第 n 个皇后
         * @return
         */
        private boolean judge(int n) {
            for (int i = 0; i < n; i++) {
                //如果他们的摆放位置一样，说明是在同一列
                /*
                  检测是否是同一斜列
                  下标: 代表的是第几行
                  值：代表的是第几列
                  . x . . .  n = 1,value = 1
                  x . . . .  i = 0,value = 0
                  Math.abs(n - i) = 1
                  Math.abs(array[n] - array[i]) = 1

                  . . x . .  n = 1,value = 2
                  . x . . .  i = 0,value = 1
                  Math.abs(n - i) = 1
                  Math.abs(array[n] - array[i]) = 1
                */
                if (array[i] == array[n]
                        || Math.abs(n - i) == Math.abs(array[n] - array[i])
                ) return false;
            }
            return true;
        }

        /**
         * 打印皇后的位置
         */
        private void print() {
            System.out.printf("第 %02d 个结果 ：", count);
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }

        /**
         * 下面是对于判定是否是同行，同列、同一斜列的分步骤测试，比较好理解
         */
        public void judgeTest() {
            /*
             * . . . . . . . .
             * x . . . . . . .
             */
            Queue8 queue8 = new Queue8();
            queue8.array[0] = 0;

            //======== 放置第 1 个皇后
            // 判断是否是同一列
            /*
             * x . . . . . . .  // 计划放到这里
             * x . . . . . . .
             */
            queue8.array[1] = 0; // 从第一列开始放置
            System.out.println("同一列，是否通过：" + queue8.judge(1));

            /*
             * . x . . . . . .  // 计划放到这里
             * x . . . . . . .
             */
            queue8.array[1] = 1;
            // 第一列不行，放置到第 2 列上
            System.out.println("同一斜列，是否通过：" + queue8.judge(1));

            /*
             * . . x . . . . .  // 计划放到这里
             * x . . . . . . .
             */
            queue8.array[1] = 2;
            // 第 2 列不行，放置到第 3 列上,这个肯定是可以的
            System.out.println("同一列或同一斜列，是否通过：" + queue8.judge(1));

            //======== 放置第 3 个皇后
            /*
             * x . . . . . . .  // 计划放到这里
             * . . x . . . . .
             * x . . . . . . .
             */
            queue8.array[2] = 0;
            // 与第一行的在同一列上了
            System.out.println("同一列，是否通过：" + queue8.judge(2));

            /*
             * . x . . . . . .  // 计划放到这里
             * . . x . . . . .
             * x . . . . . . .
             */
            queue8.array[2] = 1;
            // 第一列不行，放置到第 2 列
            // 这里与第 2 行的同一斜列了，也是不行的
            System.out.println("同一斜列，是否通过：" + queue8.judge(2));
        }
    }
}
